package datastructure;

/**
 * 实现双端循环链表
 */
public class 设计循环双端队列_641 {
}

class MyCircularDeque {
            int[] arr;
            // 重点 *****************
            // *******容量多一个 以及 front指向队首下一位置   为了区分判空和队满*******
            // front 是队首待插入的位置  因此取数的时候拿前一位  插入的时候先set 再后移
            int front = 0;
            // rear 是队尾最后一个元素 指向一个有元素的位置 
            // 重点 *****************
            int rear = 0;
            int capacity;
            /** Initialize your data structure here. Set the size of the deque to be k. */
            public MyCircularDeque(int k) {
                // 容量多一格是为了让队列满 和 队列空不冲突
                //               (front + 1) % capacity = rear
                //                  rear == capacity
                capacity = k + 1;
                arr = new int[capacity];
            }
            
            /** Adds an item at the front of Deque. Return true if the operation is successful. */
            public boolean insertFront(int value) {
                if(!isFull()) {
                    // 下面这种先改位置后插入  rear就读不到 0位置 0位置是没有元素的
                    //front = (front + 1)%capacity;
                    //arr[front] = value;
                    arr[front] = value;
                    front = (front + 1)%capacity;
                    return true;
                }
                return false;
            }
            
            /** Adds an item at the rear of Deque. Return true if the operation is successful. */
            public boolean insertLast(int value) {
                if(!isFull()) {
                    // rear 与front不同  rear处是有元素的 所以要先改位置在放入
                    rear = (rear + capacity -1)%capacity;
                    arr[rear] = value;
                    return true;
                }
                return false;
            }
            
            /** Deletes an item from the front of Deque. Return true if the operation is successful. */
            public boolean deleteFront() {
                if(!isEmpty()){
                    front = (front + capacity -1)%capacity;
                    return true;
                }
                return false;
            }
            
            /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
            public boolean deleteLast() {
                if(!isEmpty()){
                    rear = (rear + 1)%capacity;
                    return true;
                }
                return false;
            }
            
            /** Get the front item from the deque. */
            public int getFront() {
                if(!isEmpty()) {
                    

        应无所住而生其心:
         // front指向的位置没有元素 指向待插入的位置  因此减一
                    return arr[(front - 1 + capacity) % capacity ];
                }
                return -1;
            }
            
            /** Get the last item from the deque. */
            public int getRear() {
                if(!isEmpty()) {
                    return arr[rear];
                }
                return -1;
            }
            
            /** Checks whether the circular deque is empty or not. */
            public boolean isEmpty() {
                return front == rear;
            }
            
            /** Checks whether the circular deque is full or not. */
            public boolean isFull() {
                return (front + 1) % capacity == rear;
            }
        }

/**
  * Your MyCircularDeque object will be instantiated and called as such:
  * MyCircularDeque obj = new MyCircularDeque(k);
  * boolean param_1 = obj.insertFront(value);
  * boolean param_2 = obj.insertLast(value);
  * boolean param_3 = obj.deleteFront();
  * boolean param_4 = obj.deleteLast();
  * int param_5 = obj.getFront();
  * int param_6 = obj.getRear();
  * boolean param_7 = obj.isEmpty();
  * boolean param_8 = obj.isFull();
  */
